package com.breeze.leetcode.middle;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yangzh
 * @url <a href="https://leetcode.cn/problems/detect-cycles-in-2d-grid">1559. 二维网格图中探测环</a>
 * @date 2025/2/27
 */
public class T1559 {

    public static void main(String[] args) {

        char[][] grid = {{'c','c','c','a'},{'c','d','c','c'},{'c','c','e','c'},{'f','c','c','c'}};
        T1559 solution = new T1559();
        System.out.println(solution.containsCycle(grid));
    }

    public boolean containsCycle(char[][] grid) {
        List<Position> path;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                path = new ArrayList<>();
                boolean flag = dfs(null, new Position(i, j, grid), path);
                if (flag) return true;
            }
        }
        return false;
    }

    public boolean dfs(Position from, Position current, List<Position> path) {
        if (from != null && path.contains(current)) {
            return true;
        }
        path.add(current);

        boolean flag;
        List<Position> nextSteps = current.nextSteps();
        for (Position next : nextSteps) {
            if (!next.equals(from)) {
                flag = dfs(current, next, path);
                if (flag) return true;
                else path.remove(next);
            }

        }

        return false;
    }

    static class Position {
        int row;
        int col;
        char value;
        char[][] grid;

        public Position(int row, int col, char[][] grid) {
            this.row = row;
            this.col = col;
            this.value = grid[row][col];
            this.grid = grid;
        }

        public List<Position> nextSteps() {
            List<Position> steps = new ArrayList<>();
            if (col > 0 && grid[row][col - 1] == value) steps.add(new Position(row, col - 1, grid));
            if (row > 0 && grid[row - 1][col] == value) steps.add(new Position(row - 1, col, grid));
            if (row < grid.length - 1 && grid[row + 1][col] == value) steps.add(new Position(row + 1, col, grid));
            if (col < grid[0].length - 1 && grid[row][col + 1] == value) steps.add(new Position(row, col + 1, grid));
            return steps;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Position pos) {
                return row == pos.row && col == pos.col;
            }
            return false;
        }
    }
}
